package org.example.y24.m10;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class CityPair implements Comparable<CityPair> {
    int north;
    int south;

    public CityPair(int north, int south) {
        this.north = north;
        this.south = south;
    }

    @Override
    public int compareTo(CityPair other) {
        return Integer.compare(this.north, other.north);
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("请输入城市数量 N：");
        int N;
        while (!scanner.hasNextInt() || (N = scanner.nextInt()) <= 0) {
            scanner.nextLine();
            System.out.print("无效的城市数量，请输入一个正整数：");
        }

        ArrayList<CityPair> pairs = new ArrayList<>(N);
        System.out.println("请依次输入每对友好城市的位置（北岸位置 南岸位置）：");
        for (int i = 0; i < N; i++) {
            while (!scanner.hasNextInt()) {
                scanner.next();
            }
            int north = scanner.nextInt();
            if (!scanner.hasNextInt()) {
                scanner.next();
            }
            int south = scanner.nextInt();
            pairs.add(new CityPair(north, south));
        }

        Collections.sort(pairs);

        int[] southSeq = new int[N];
        for (int i = 0; i < N; i++) {
            southSeq[i] = pairs.get(i).south;
        }

        ArrayList<Integer> tails = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int index = Collections.binarySearch(tails, southSeq[i]);
            if (index < 0) {
                index = -(index + 1);
            }
            if (index == tails.size()) {
                tails.add(southSeq[i]);
            } else {
                tails.set(index, southSeq[i]);
            }
        }

        System.out.println("最大可批准的航线数量：" + tails.size());

        scanner.close();
    }
}
